package cxydmmszl.chapter04.t062;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * <li style="color: red;">Prob</li>
 * 最长递增子序列
 * <li style="color: red;">Desc</li>
 * 给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中字典序最小的）
 * 输入描述：<br/><br/>
 * 输出两行，第一行包括一个正整数 n(n<=100000)，代表数组长度。
 * 第二行包括 n 个整数，代表数组 arr(1≤arr[i]≤1e9)。<br/><br/>
 * 输出描述：<br/>
 * 输出一行。代表你求出的最长的递增子序列。
 * <li style="color: red;">Link</li> CD25
 *
 * @author habitplus
 * @since 2021-09-02 22:31
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        if (n < 1) {
            System.out.println();
            bf.close();
            return;
        }

        int[] arr = new int[n];
        String[] ss = bf.readLine().split(" ");
        bf.close();

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(ss[i]);
        }

        int[] ans = longestSubArr(arr);

        for (int e : ans) {
            System.out.print(e + " ");
        }
    }

    public static int[] longestSubArr(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new int[0];
        }
        int[] dp = maxLength2(arr);
        return generateLIS(arr, dp);

        // 寻找最大的长度的下标
//        int k = 0;
//        for (int i = 0; i < dp.length; i++) {
//            if (dp[i] > dp[k]) {
//                k = i;
//            }
//        }
//
//
//        int len = dp[k];
//        int[] ans = new int[len];
//        for (int i = k; i >= 0; i--) {
//            if (dp[i] == len) {
//                if (arr[k] > arr[i]) {
//                    k = i;
//                }
//            } else if (dp[i] == len - 1) {
//                ans[--len] = arr[k];
//                k = i;
//            }
//        }
//        ans[--len] = arr[k];
//
//        return ans;
    }

    private static int[] generateLIS(int[] arr, int[] dp) {
        int len = 0;
        int index = 0;
        int pre = Integer.MAX_VALUE;
        for (int i = 0; i < dp.length; i++) {
            if (dp[i] > len) {
                len = dp[i];
                index = i;
                pre = arr[i];
            } else if (dp[i] == len) {
                if (arr[i] < pre) {
                    pre = arr[i];
                    len = dp[i];
                    index = i;
                }
            }
        }
        int[] lis = new int[len];
        lis[--len] = arr[index];
        for (int i = index; i >= 0; i--) {
            if (arr[i] < arr[index] && dp[i] == dp[index] - 1) {
                lis[--len] = arr[i];
                index = i;
            }
        }
        return lis;
    }

    // 时间复杂度： O(NlogN)
    private static int[] maxLength2(int[] arr) {

        int n = arr.length;
        // ends[i] 表示以 arr[i] 结尾的最长递增子序列的长度为 i+1
        int[] ends = new int[n];
        int[] dp = new int[n];
        int right = 0;
        int l, r, m;
        dp[0] = 1;
        ends[0] = arr[0];

        for (int i = 1; i < n; i++) {
            l = 0;
            r = right;

            while (l <= r) {
                m = (l + r) / 2;
                if (ends[m] < arr[i]) {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }

            right = Math.max(l, right);
            ends[l] = arr[i];
            dp[i] = l + 1;
        }
        return dp;
    }

    // 时间复杂度：O(N^2)
    private static int[] maxLength1(int[] arr) {
        // dp[i] 表示以 arr[i] 结尾的情况下最长子序列的长度
        int n = arr.length;
        int[] dp = new int[n];

        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            dp[i] = 1;
            for (int j = i - 1; j >= 0; j--) {
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        return dp;
    }

}
